This invention relates generally to computer systems and more particularly to mapping of registers provided in pipelined computers.
As it is known in the art, computer systems have become ubiquitous. In particular, one type of computer system widely employed is the so-called pipeline processor. In a pipeline processor, processor actions are decomposed into a plurality of steps in order to increase throughput. As an example of pipelining, a pipelined instruction stage decomposes instructions into assembly like stages. Illustratively, a pipeline stage includes an instruction fetch stage in which instructions are fetched in one or several cycles from a cache memory, and instruction decode stage in which the op code of the instruction, that is the portion of the code which determines the function of the instruction is examined to ascertain the function as well as the resources needed by the instruction. Illustrative examples of resources may include general purpose registers within the CPU, access to internal buses and external buses, and functional units such as I/O units and arithmetic logic units and so forth.
A third stage is typically the instruction issue stage in which resource availability is checked for each instruction and resources are reserved for particular instructions. The fourth stage of a typical parallel pipeline computer system is the execution stage in which instructions are executed in one or several pipelined execution stages typically writing results into or reading results from general purpose registers during the last execution stage.
In an ideal pipeline processor, time is measured in CPU clock periods. In theory, the clock period for a P-stage pipeline would be 1/P of the clock period for a non-pipelined equivalent since the non-pipeline equivalent would have P-1 less stages of execution for the instruction. Thus, with the pipelined approach there is the potential for a P times increase in throughput or performance improvement over a conventional non-pipelined architecture.
There are several practical limitations on pipeline performance however which prevents a pipeline processor from achieving a times P throughput improvement.
With instruction pipelined stages and pipelined computer systems in general, there is a delay until actions are taken while the various pipelines within the computer system are filled. Thus, it is desirable to keep the pipeline full so that each stage in the pipeline be it in the instruction segment, execution segment, or the cache segment is processing in order to utilize a pipeline processor to its fullest advantage.
To maintain the pipeline full for as long a period as possible the pipeline processor often requires circuits to provide predictions such as which sequence of instructions to follow when processing a branch type of instruction. If the prediction concerning the instructions sequence is correct executions of the instruction follows without incident. However if a wrong path of the instruction sequence is followed after a conditional branch instruction then the pipeline must be backed up to the conditional branch instruction and the instructions of the correct path are required to be loaded into the pipeline. For execution, it is required that all of the operands that were previously used in the pipeline at the time prior to the execution of the conditional branch must be restored to the pipeline.
One of the problems that arises with backing up of the pipeline is that the values of the registers used in the execution of the instructions in general will change between the time the conditional branch instruction is performed and the time the error condition which indicated that the conditional branch taken was incorrect is recognized.
In modern computers, registers are used to store values of operands. A typical instruction processed by a pipeline will add the values stored in two different registers and place the resulting value in one of the two registers or a third register. For example, an instruction may be "add R7, R8&gt;R9" this instruction is interpreted to mean that the contents of register 7 as well as the contents of register 8 are added together and the result is placed in the register 9. The problem with pipelined systems, conditional branches, and the use of registers is that often a subsequent instruction will change the contents of a register as it passes through the pipeline. Thus, as an example, assuming a latter or subsequent instruction following the instruction "add R8&gt;R9" is an instruction add R1, R2&gt;R7. By executing the second subsequent instruction the contents of register 7 have been changed. If it is necessary to back up the instruction stage to the first instruction add R8&gt;R9 as a result of the conditional branch mispredict or other condition in the central processing unit, the contents of R7 which were changed by the second subsequent instruction add R1, R2&gt;R7 will now provide an incorrect result. Thus, in general it would not be possible to back up the instruction pipeline to the instruction add R7, R8&gt;R9 and provide a valid result in register R9. That is, if the first instruction in which the contents of register 7 and register 8 are added were to be performed after execution of the second instruction due to a back up of the pipelined processor the resulting value stored in R9 would be different than the value which should have been stored in
As it is also known in the art, in pipeline computer systems many instructions can be processed through the pipeline before a misprediction or other trapped condition is recognized by control logic in the pipeline computer. The value contained in any one of the registers which may be used by the set of instructions many have changed may times before the trapped condition is recognized. Therefore, there is a need to save the contents of registers for instructions until the instructions are past the time that a trap or other condition could cause the pipeline to be backed up to any of those instructions.
One approach for saving the contents of registers is "register renaming" or register mapping. In register renaming there are a plurality of registers for example 32 which can be used by instructions executed by the pipeline. These registers are referred to as logical registers. With register renaming, logical registers are mapped to a new physical register (i.e. home). Each result provided for a logical register is given a new physical home in the pool of registers. Typically, the new assignment of registers is kept in a register file. Thus, multiple generations of the same logical register will be available and held in different physical homes in the register file.
In order to implement a register renaming scheme an apparatus is provided to determine what physical home holds the latest value for each logical register. This apparatus is generally referred to as a register map. In addition, it is possible to restore the state of the register map to a state that the map was in at some time to be able to effectively back the pipeline up to that state and process instructions again from that state.
In long pipeline computers that can issue and operate on a plurality of instructions in parallel, so-called super-scalar architecture computers, it is necessary to back up a plurality of instructions in parallel, with the plurality of instructions being at least equal to the plurality of instructions which can be executed by the super-scalar computer. Present approaches do not in general provide an effective solution to saving a plurality of registers for a plurality of instructions.